/*
 * @(#)Shudu.java		       Project:Tools
 * Date:2012-7-2
 *
 * Copyright (c) 2011 CFuture09, Institute of Software, 
 * Guangdong Ocean University, Zhanjiang, GuangDong, China.
 * All rights reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.sinaapp.msdxblog.tools.shudu;

import java.awt.Point;

/**
 * @author Geek_Soledad (66704238@51uc.com)
 */
public class Sodoku {
	private int n = 0;
	public static final int[][] body = { { 8, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 3, 6, 0, 0, 0, 0, 0 }, { 0, 7, 0, 0, 9, 0, 2, 0, 0 },
			{ 0, 5, 0, 0, 0, 7, 0, 0, 0 }, { 0, 0, 0, 0, 4, 5, 7, 0, 0 },
			{ 0, 0, 0, 1, 0, 0, 0, 3, 0 }, { 0, 0, 1, 0, 0, 0, 0, 6, 8 },
			{ 0, 0, 8, 5, 0, 0, 0, 1, 0 }, { 0, 9, 0, 0, 0, 0, 4, 0, 0 } };

	public void calculate(int[][] data, int row, int col, int currentValue) {
		System.out.println(n++);
		int nextValue = findNextValue(data, row, col, currentValue);
		do {
			if (nextValue == -1) {
				data[row][col] = body[row][col];
				if (row == 8 && col == 8) {
					System.out.println("无解");
				}
				return;
			} else {
				data[row][col] = nextValue;
			}
			if (row == 8 && col == 8) {
				printResult(data);
				break;
			}

			Point point = nextPlace(row, col + 1);
			if (point == null) {
				System.out.println("无解！");
				return;
			}
			calculate(data, point.x, point.y, data[point.x][point.y]);
			nextValue = findNextValue(data, row, col, nextValue);
		} while (nextValue != -1);
		data[row][col] = body[row][col];
	}

	/**
	 * 下一个进行计算的位置。
	 * 
	 * @param row
	 * @param col
	 * @return
	 */
	public Point nextPlace(int row, int col) {
		if (col >= 9) {
			row++;
			col = 0;
		}
		while (row < 9 && col < 9) {
			if (body[row][col] == 0) {
				System.out.println(row + "..." + col);
				return new Point(row, col);
			}
			col++;
			if (col >= 9) {
				row++;
				col = 0;
			}
		}
		return null;
	}

	/**
	 * 找出下一个符合条件的数字。
	 * 
	 * @param data
	 *            数独数组。
	 * @param row
	 *            行
	 * @param col
	 *            列
	 * @param currentValue
	 *            当前的数字。
	 * @return 返回下一个符合条件的数字。当没有符合条件的数字时，返回-1。
	 */
	private int findNextValue(final int[][] data, final int row, final int col,
			final int currentValue) {
		int nextvalue = currentValue;
		do {
			nextvalue++;
			// 检查当行是否存在该数字
			if (whetherExistInRow(data, row, col, nextvalue)) {
				continue;
			}
			// 检查当列是否存在该数字
			if (whetherExistInCol(data, row, col, nextvalue)) {
				continue;
			}
			// 检查所在九宫格是否存在该数字
			if (whetherExistInSquare(data, row, col, nextvalue)) {
				continue;
			}
			break;
		} while (nextvalue < 9);
		if (nextvalue >= 9) {
			return -1;
		}
		return nextvalue;
	}

	/**
	 * 所在行是否存在该数字。
	 * 
	 * @param data
	 * @param row
	 * @param col
	 * @param value
	 * @return
	 */
	private boolean whetherExistInRow(final int[][] data, final int row,
			final int col, final int value) {
		for (int i = 0; i < 9; i++) {
			if (i == col) {
				continue;
			}
			if (value == data[row][i]) {
				return true;
			}
		}
		return false;
	}

	/**
	 * 所在列是否存在该数字。
	 * 
	 * @param data
	 * @param row
	 * @param col
	 * @param value
	 * @return
	 */
	private boolean whetherExistInCol(final int[][] data, final int row,
			final int col, final int value) {
		for (int i = 0; i < 9; i++) {
			if (i == row) {
				continue;
			}
			if (value == data[i][col]) {
				return true;
			}
		}
		return false;
	}

	/**
	 * 所在九宫格中是否存在该数字
	 * 
	 * @param data
	 * @param row
	 * @param col
	 * @param value
	 * @return
	 */
	private boolean whetherExistInSquare(final int[][] data, final int row,
			final int col, final int value) {
		int x = row / 3 * 3;
		int y = col / 3 * 3;
		for (int i = x; i < x + 3; i++) {
			for (int j = y; j < y + 3; j++) {
				if (i == row && j == col) {
					continue;
				}
				if (data[i][j] == value) {
					return true;
				}
			}
		}
		return false;
	}

	protected void printResult(int[][] data) {
		for (int i = 0; i < data.length; i++) {
			if (i == 3 || i == 6) {
				System.out.println("-------------------");
			}
			for (int j = 0; j < data[i].length; j++) {
				if (j == 3 || j == 6) {
					System.out.print("|");
				}
				System.out.print(data[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		Sodoku sodoku = new Sodoku();
		Point point = sodoku.nextPlace(0, 0);
		sodoku.calculate(body.clone(), point.x, point.y, 0);
	}
}
